home *** CD-ROM | disk | FTP | other *** search
/ Linux Cubed Series 4: GNU Archives / Linux Cubed Series 4 - GNU Archives.iso / gnu / id-utils.2 / id-utils / id-utils-3.2 / src / mkid.c < prev    next >
Encoding:
C/C++ Source or Header  |  1996-07-09  |  21.6 KB  |  830 lines
  1. /* mkid.c -- build an identifer database
  2.    Copyright (C) 1986, 1995, 1996 Free Software Foundation, Inc.
  3.    Written by Greg McGary <gkm@gnu.ai.mit.edu>
  4.  
  5.    This program is free software; you can redistribute it and/or modify
  6.    it under the terms of the GNU General Public License as published by
  7.    the Free Software Foundation; either version 2, or (at your option)
  8.    any later version.
  9.  
  10.    This program is distributed in the hope that it will be useful,
  11.    but WITHOUT ANY WARRANTY; without even the implied warranty of
  12.    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13.    GNU General Public License for more details.
  14.  
  15.    You should have received a copy of the GNU General Public License
  16.    along with this program; if not, write to the Free Software
  17.    Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */
  18.  
  19. #include <config.h>
  20. #include "xstdlib.h"
  21. #include <assert.h>
  22. #include <stdio.h>
  23. #include <errno.h>
  24. #include <getopt.h>
  25. #include "xsysstat.h"
  26. #include "xstddef.h"
  27. #include "xunistd.h"
  28. #include "xnls.h"
  29. #include "pathmax.h"
  30. #include "xstring.h"
  31. #include "idfile.h"
  32. #include "xmalloc.h"
  33. #include "hash.h"
  34. #include "scanners.h"
  35. #include "error.h"
  36. #include "xalloca.h"
  37. #if HAVE_LIMITS_H
  38. # include <limits.h>
  39. #endif
  40.  
  41. struct summary
  42. {
  43.   struct token **sum_tokens;
  44.   unsigned char const *sum_hits;
  45.   struct summary *sum_parent;
  46.   union {
  47.     struct summary *u_kids[8];    /* when sum_level > 0 */
  48. #define sum_kids sum_u.u_kids
  49.     struct member_file *u_files[8];    /* when sum_level == 0 */
  50. #define sum_files sum_u.u_files
  51.   } sum_u;
  52.   unsigned long sum_tokens_size;
  53.   unsigned long sum_hits_count;
  54.   int sum_free_index;
  55.   int sum_level;
  56. };
  57.  
  58. void usage __P((void));
  59. static void help_me __P((void));
  60. int main __P((int argc, char **argv));
  61. void assert_writeable __P((char const *file_name));
  62. void scan_files __P((struct idhead *idhp));
  63. void scan_member_file __P((struct member_file const *member));
  64. void scan_member_file_1 __P((get_token_func_t get_token, void const *args, FILE *source_FILE));
  65. void report_statistics __P((void));
  66. void write_id_file __P((struct idhead *idhp));
  67. unsigned long token_hash_1 __P((void const *key));
  68. unsigned long token_hash_2 __P((void const *key));
  69. int token_hash_cmp __P((void const *x, void const *y));
  70. int token_qsort_cmp __P((void const *x, void const *y));
  71. void bump_current_hits_signature __P((void));
  72. void init_hits_signature __P((int i));
  73. void free_summary_tokens __P((void));
  74. void summarize __P((void));
  75. void init_summary __P((void));
  76. struct summary *make_sibling_summary __P((struct summary *summary));
  77. int count_vec_size __P((struct summary *summary, unsigned char const *tail_hits));
  78. int count_buf_size __P((struct summary *summary, unsigned char const *tail_hits));
  79. void assert_hits __P((struct summary* summary));
  80. void write_hits __P((FILE *fp, struct summary *summary, unsigned char const *tail_hits));
  81. void sign_token __P((struct token *token));
  82. void add_token_to_summary __P((struct summary *summary, struct token *token));
  83.  
  84. struct hash_table token_table;
  85.  
  86. /* Miscellaneous statistics */
  87. size_t input_chars;
  88. size_t name_tokens;
  89. size_t number_tokens;
  90. size_t string_tokens;
  91. size_t literal_tokens;
  92. size_t comment_tokens;
  93. size_t occurrences;
  94. size_t hits_length = 0;
  95. size_t tokens_length = 0;
  96. size_t output_length = 0;
  97.  
  98. int verbose_flag = 0;
  99. int statistics_flag = 0;
  100.  
  101. int file_name_count = 0;    /* # of files in database */
  102. int levels = 0;            /* ceil(log(8)) of file_name_count */
  103.  
  104. unsigned char current_hits_signature[MAX_LEVELS];
  105. #define INIT_TOKENS_SIZE(level) (1 << ((level) + 13))
  106. struct summary *summary_root;
  107. struct summary *summary_leaf;
  108.  
  109. char const *program_name;
  110.  
  111. char *lang_map_file_name = 0;
  112. int show_version = 0;
  113. int show_help = 0;
  114. struct idhead idh;
  115. struct file_link *cw_dlink;
  116.  
  117. void
  118. usage (void)
  119. {
  120.   fprintf (stderr, _("Try `%s --help' for more information.\n"),
  121.        program_name);
  122.   exit (1);
  123. }
  124.  
  125. static struct option const long_options[] =
  126. {
  127.   { "file", required_argument, 0, 'f' },
  128.   { "output", required_argument, 0, 'o' },
  129.   { "include", required_argument, 0, 'i' },
  130.   { "exclude", required_argument, 0, 'x' },
  131.   { "lang-option", required_argument, 0, 'l' },
  132.   { "lang-map", required_argument, 0, 'm' },
  133.   { "default-lang", required_argument, 0, 'd' },
  134.   { "prune", required_argument, 0, 'p' },
  135.   { "verbose", no_argument, 0, 'v' },
  136.   { "statistics", no_argument, 0, 's' },
  137.   { "help", no_argument, &show_help, 1 },
  138.   { "version", no_argument, &show_version, 1 },
  139.   { 0 }
  140. };
  141.  
  142. static void
  143. help_me (void)
  144. {
  145.   printf (_("\
  146. Usage: %s [OPTION]... [FILE]...\n\
  147. "), program_name);
  148.  
  149.   printf (_("\
  150. Build an identifier database.\n\
  151.   -o, --output=OUTFILE    file name of ID database output\n\
  152.   -f, --file=OUTFILE      synonym for --output\n\
  153.   -i, --include=LANGS     include languages in LANGS (default: \"C C++ asm\")\n\
  154.   -x, --exclude=LANGS     exclude languages in LANGS\n\
  155.   -l, --lang-option=L:OPT pass OPT as a default for language L (see below)\n\
  156.   -m, --lang-map=MAPFILE  use MAPFILE to map file names onto source language\n\
  157.   -d, --default-lang=LANG make LANG the default source language\n\
  158.   -p, --prune=NAMES       exclude the named files and/or directories\n\
  159.   -v, --verbose           report per file statistics\n\
  160.   -s, --statistics        report statistics at end of run\n\
  161. \n\
  162.       --help              display this help and exit\n\
  163.       --version           output version information and exit\n\
  164. \n\
  165. FILE may be a file name, or a directory name to recursively search.\n\
  166. If no FILE is given, the current directory is searched by default.\n\
  167. Note that the `--include' and `--exclude' options are mutually-exclusive.\n\
  168. \n\
  169. The following arguments apply to the language-specific scanners:\n\
  170. "));
  171.   language_help_me ();
  172.   exit (0);
  173. }
  174.  
  175. char const *heap_initial;
  176. char const *heap_after_walk;
  177. char const *heap_after_scan;
  178.  
  179. int
  180. main (int argc, char **argv)
  181. {
  182.   program_name = argv[0];
  183.   heap_initial = (char const *) sbrk (0);
  184.   idh.idh_file_name = DEFAULT_ID_FILE_NAME;
  185.  
  186.   /* Set locale according to user's wishes.  */
  187.   setlocale (LC_ALL, "");
  188.  
  189.   /* Tell program which translations to use and where to find.  */
  190.   bindtextdomain (PACKAGE, LOCALEDIR);
  191.   textdomain (PACKAGE);
  192.  
  193.   for (;;)
  194.     {
  195.       int optc = getopt_long (argc, argv, "o:f:i:x:l:m:d:p:vs",
  196.                   long_options, (int *) 0);
  197.       if (optc < 0)
  198.     break;
  199.       switch (optc)
  200.     {
  201.     case 0:
  202.       break;
  203.  
  204.     case 'o':
  205.     case 'f':
  206.       idh.idh_file_name = optarg;
  207.       break;
  208.  
  209.     case 'i':
  210.       include_languages (optarg);
  211.       break;
  212.  
  213.     case 'x':
  214.       exclude_languages (optarg);
  215.       break;
  216.  
  217.     case 'l':
  218.       language_save_arg (optarg);
  219.       break;
  220.  
  221.     case 'm':
  222.       lang_map_file_name = optarg;
  223.       break;
  224.  
  225.     case 'd':
  226.       set_default_language (optarg);
  227.       break;
  228.  
  229.     case 'p':
  230.       if (cw_dlink == 0)
  231.         cw_dlink = init_walker (&idh);
  232.       prune_file_names (optarg, cw_dlink);
  233.       break;
  234.  
  235.     case 'v':
  236.       verbose_flag = 1;
  237.       statistics_flag = 1;
  238.       break;
  239.  
  240.     case 's':
  241.       statistics_flag = 1;
  242.       break;
  243.  
  244.     default:
  245.       usage ();
  246.     }
  247.     }
  248.  
  249.   if (show_version)
  250.     {
  251.       printf ("%s - %s\n", program_name, PACKAGE_VERSION);
  252.       exit (0);
  253.     }
  254.  
  255.   if (show_help)
  256.     help_me ();
  257.  
  258.   argc -= optind;
  259.   argv += optind;
  260.   if (argc == 0)
  261.     {
  262.       static char *dot = (char *) ".";
  263.       argc = 1;
  264.       argv = ˙
  265.     }
  266.  
  267.   language_getopt ();
  268.   assert_writeable (idh.idh_file_name);
  269.   if (cw_dlink == 0)
  270.     cw_dlink = init_walker (&idh);
  271.   parse_language_map (lang_map_file_name);
  272.  
  273.   while (argc--)
  274.     {
  275.       struct file_link *flink = parse_file_name (*argv++, cw_dlink);
  276.       if (flink)
  277.     walk_flink (flink, 0);
  278.     }
  279.   heap_after_walk = (char const *) sbrk (0);
  280.  
  281.   mark_member_file_links (&idh);
  282.   if (idh.idh_member_file_table.ht_fill)
  283.     {
  284.       scan_files (&idh);
  285.       heap_after_scan = sbrk (0);
  286.  
  287.       free_summary_tokens ();
  288.       free (token_table.ht_vec);
  289.       chdir_to_link (cw_dlink);
  290.       write_id_file (&idh);
  291.  
  292.       if (statistics_flag)
  293.     report_statistics ();
  294.     }
  295.   else
  296.     error (0, 0, "nothing to do");
  297.   exit (0);
  298. }
  299.  
  300. void
  301. assert_writeable (char const *file_name)
  302. {
  303.   if (access (file_name, 06) < 0)
  304.     {
  305.       if (errno == ENOENT)
  306.     {
  307.       char const *dir_name = dirname (file_name);
  308.       if (!dir_name || !*dir_name)
  309.         dir_name = ".";
  310.       if (access (dir_name, 06) < 0)
  311.         error (1, errno, _("can't create `%s' in `%s'"),
  312.            basename (file_name), dir_name);
  313.     }
  314.       else
  315.     error (1, errno, _("can't modify `%s'"), file_name);
  316.     }
  317. }
  318.  
  319. void
  320. scan_files (struct idhead *idhp)
  321. {
  322.   struct member_file **members_0
  323.     = (struct member_file **) hash_dump (&idhp->idh_member_file_table,
  324.                      0, member_file_qsort_compare);
  325.   struct member_file **end = &members_0[idhp->idh_member_file_table.ht_fill];
  326.   struct member_file **members = members_0;
  327.  
  328.   hash_init (&token_table, idhp->idh_member_file_table.ht_fill * 64,
  329.          token_hash_1, token_hash_2, token_hash_cmp);
  330.   init_hits_signature (0);
  331.   init_summary ();
  332.   obstack_init (&tokens_obstack);
  333.  
  334.   for (;;)
  335.     {
  336.       struct member_file *member = *members++;
  337.       scan_member_file (member);
  338.       if (members == end)
  339.     break;
  340.       if (current_hits_signature[0] & 0x80)
  341.     summarize ();
  342.       bump_current_hits_signature ();
  343.     }
  344.  
  345.   free (members_0);
  346. }
  347.  
  348. void
  349. scan_member_file (struct member_file const *member)
  350. {
  351.   struct lang_args const *lang_args = member->mf_lang_args;
  352.   struct language const *lang = lang_args->la_language;
  353.   get_token_func_t get_token = lang->lg_get_token;
  354.   struct file_link *flink = member->mf_link;
  355.   struct stat st;
  356.   FILE *source_FILE;
  357.  
  358.   chdir_to_link (flink->fl_parent);
  359.   source_FILE = fopen (flink->fl_name, "r");
  360.   if (source_FILE)
  361.     {
  362.       if (statistics_flag)
  363.     {
  364.       if (fstat (fileno (source_FILE), &st) < 0)
  365.         {
  366.           char *file_name = ALLOCA (char, PATH_MAX);
  367.           maybe_relative_file_name (file_name, flink, cw_dlink);
  368.           error (0, errno, _("can't stat `%s'"), file_name);
  369.         }
  370.       else
  371.         input_chars += st.st_size;
  372.     }
  373.       if (verbose_flag)
  374.     {
  375.       char *file_name = ALLOCA (char, PATH_MAX);
  376.       maybe_relative_file_name (file_name, flink, cw_dlink);
  377.       printf ("%d: %s: %s", member->mf_index, lang->lg_name, file_name);
  378.       fflush (stdout);
  379.     }
  380.       scan_member_file_1 (get_token, lang_args->la_args_digested, source_FILE);
  381.       if (verbose_flag)
  382.     putchar ('\n');
  383.       fclose (source_FILE);
  384.     }
  385.   else
  386.     error (0, errno, _("can't open `%s'"), flink->fl_name);
  387. }
  388.  
  389. void
  390. scan_member_file_1 (get_token_func_t get_token, void const *args, FILE *source_FILE)
  391. {
  392.   struct token **slot;
  393.   struct token *token;
  394.   int flags;
  395.   int new_tokens = 0;
  396.   int distinct_tokens = 0;
  397.  
  398.   while ((token = (*get_token) (source_FILE, args, &flags)) != NULL)
  399.     {
  400.       if (*token->tok_name == '\0') {
  401.     obstack_free (&tokens_obstack, token);
  402.     continue;
  403.       }
  404.       slot = (struct token **) hash_find_slot (&token_table, token);
  405.       if (HASH_VACANT (*slot))
  406.     {
  407.       token->tok_flags = flags;
  408.       token->tok_count = 1;
  409.       memset (token->tok_hits, 0, sizeof (token->tok_hits));
  410.       sign_token (token);
  411.       if (verbose_flag)
  412.         {
  413.           distinct_tokens++;
  414.           new_tokens++;
  415.         }
  416.       hash_insert_at (&token_table, token, slot);
  417.     }
  418.       else
  419.     {
  420.       obstack_free (&tokens_obstack, token);
  421.       token = *slot;
  422.       token->tok_flags |= flags;
  423.       if (token->tok_count < USHRT_MAX)
  424.         token->tok_count++;
  425.       if (!(token->tok_hits[0] & current_hits_signature[0]))
  426.         {
  427.           sign_token (token);
  428.           if (verbose_flag)
  429.         distinct_tokens++;
  430.         }
  431.     }
  432.     }
  433.   if (verbose_flag)
  434.     {
  435.       printf (_("  new = %d/%d"), new_tokens, distinct_tokens);
  436.       if (distinct_tokens != 0)
  437.     printf (" = %.0f%%", 100.0 * (double) new_tokens / (double) distinct_tokens);
  438.     }
  439. }
  440.  
  441. void
  442. report_statistics (void)
  443. {
  444.   printf (_("Name=%ld, "), name_tokens);
  445.   printf (_("Number=%ld, "), number_tokens);
  446.   printf (_("String=%ld, "), string_tokens);
  447.   printf (_("Literal=%ld, "), literal_tokens);
  448.   printf (_("Comment=%ld\n"), comment_tokens);
  449.  
  450.   printf (_("Files=%d, "), idh.idh_files);
  451.   printf (_("Tokens=%ld, "), occurrences);
  452.   printf (_("Bytes=%ld Kb, "), input_chars / 1024);
  453.   printf (_("Heap=%ld+%ld Kb, "), (heap_after_scan - heap_after_walk) / 1024,
  454.       (heap_after_walk - heap_initial) / 1024);
  455.   printf (_("Output=%ld (%ld tok, %ld hit)\n"), output_length, tokens_length, hits_length);
  456.  
  457.   hash_print_stats (&token_table, stdout);
  458.   printf (_(", Freq=%ld/%ld=%.2f\n"), occurrences, token_table.ht_fill,
  459.       (double) occurrences / (double) token_table.ht_fill);
  460. }
  461.  
  462. /* As the database is written, may need to adjust the file names.  If
  463.    we are generating the ID file in a remote directory, then adjust
  464.    the file names to be relative to the location of the ID database.
  465.  
  466.    (This would be a common useage if you want to make a database for a
  467.    directory which you have no write access to, so you cannot create
  468.    the ID file.)  */
  469. void
  470. write_id_file (struct idhead *idhp)
  471. {
  472.   struct token **tokens;
  473.   int i;
  474.   int buf_size;
  475.   int vec_size;
  476.   int tok_size;
  477.   int max_buf_size = 0;
  478.   int max_vec_size = 0;
  479.  
  480.   if (verbose_flag)
  481.     printf (_("Sorting tokens...\n"));
  482.   assert (summary_root->sum_hits_count == token_table.ht_fill);
  483.   tokens = REALLOC (summary_root->sum_tokens, struct token *, token_table.ht_fill);
  484.   qsort (tokens, token_table.ht_fill, sizeof (struct token *), token_qsort_cmp);
  485.  
  486.   if (verbose_flag)
  487.     printf (_("Writing `%s'...\n"), idhp->idh_file_name);
  488.   idhp->idh_FILE = fopen (idhp->idh_file_name, "w+b");
  489.   if (idhp->idh_FILE == NULL)
  490.     error (1, errno, _("can't create `%s'"), idhp->idh_file_name);
  491.  
  492.   idhp->idh_magic[0] = IDH_MAGIC_0;
  493.   idhp->idh_magic[1] = IDH_MAGIC_1;
  494.   idhp->idh_version = IDH_VERSION;
  495.   idhp->idh_flags = IDH_COUNTS;
  496.  
  497.   /* write out the list of pathnames */
  498.  
  499.   fseek (idhp->idh_FILE, sizeof_idhead (), 0);
  500.   idhp->idh_flinks_offset = ftell (idhp->idh_FILE);
  501.   serialize_file_links (idhp);
  502.  
  503.   /* write out the list of identifiers */
  504.  
  505.   putc ('\0', idhp->idh_FILE);
  506.   putc ('\0', idhp->idh_FILE);
  507.   idhp->idh_tokens_offset = ftell (idhp->idh_FILE);
  508.  
  509.   for (i = 0; i < token_table.ht_fill; i++, tokens++)
  510.     {
  511.       struct token *token = *tokens;
  512.       occurrences += token->tok_count;
  513.       if (token->tok_flags & TOK_NUMBER)
  514.     number_tokens++;
  515.       if (token->tok_flags & TOK_NAME)
  516.     name_tokens++;
  517.       if (token->tok_flags & TOK_STRING)
  518.     string_tokens++;
  519.       if (token->tok_flags & TOK_LITERAL)
  520.     literal_tokens++;
  521.       if (token->tok_flags & TOK_COMMENT)
  522.     comment_tokens++;
  523.  
  524.       fputs (token->tok_name, idhp->idh_FILE);
  525.       putc ('\0', idhp->idh_FILE);
  526.       if (token->tok_count > 0xff)
  527.     token->tok_flags |= TOK_SHORT_COUNT;
  528.       putc (token->tok_flags, idhp->idh_FILE);
  529.       putc (token->tok_count & 0xff, idhp->idh_FILE);
  530.       if (token->tok_flags & TOK_SHORT_COUNT)
  531.     putc (token->tok_count >> 8, idhp->idh_FILE);
  532.  
  533.       vec_size = count_vec_size (summary_root, token->tok_hits + levels);
  534.       buf_size = count_buf_size (summary_root, token->tok_hits + levels);
  535.       hits_length += buf_size;
  536.       tok_size = strlen (token->tok_name) + 1;
  537.       tokens_length += tok_size;
  538.       buf_size += tok_size + sizeof (token->tok_flags) + sizeof (token->tok_count) + 2;
  539.       if (buf_size > max_buf_size)
  540.     max_buf_size = buf_size;
  541.       if (vec_size > max_vec_size)
  542.     max_vec_size = vec_size;
  543.  
  544.       write_hits (idhp->idh_FILE, summary_root, token->tok_hits + levels);
  545.       putc ('\0', idhp->idh_FILE);
  546.       putc ('\0', idhp->idh_FILE);
  547.     }
  548.   assert_hits (summary_root);
  549.   idhp->idh_tokens = token_table.ht_fill;
  550.   output_length = ftell (idhp->idh_FILE);
  551.   idhp->idh_end_offset = output_length - 2;
  552.   idhp->idh_buf_size = max_buf_size;
  553.   idhp->idh_vec_size = max_vec_size;
  554.  
  555.   write_idhead (&idh);
  556.   fclose (idhp->idh_FILE);
  557. }
  558.  
  559. unsigned long
  560. token_hash_1 (void const *key)
  561. {
  562.   return_STRING_HASH_1 (((struct token const *) key)->tok_name);
  563. }
  564.  
  565. unsigned long
  566. token_hash_2 (void const *key)
  567. {
  568.   return_STRING_HASH_2 (((struct token const *) key)->tok_name);
  569. }
  570.  
  571. int
  572. token_hash_cmp (void const *x, void const *y)
  573. {
  574.   return_STRING_COMPARE (((struct token const *) x)->tok_name,
  575.              ((struct token const *) y)->tok_name);
  576. }
  577.  
  578. int
  579. token_qsort_cmp (void const *x, void const *y)
  580. {
  581.   return_STRING_COMPARE ((*(struct token const *const *) x)->tok_name,
  582.              (*(struct token const *const *) y)->tok_name);
  583. }
  584.  
  585.  
  586. /****************************************************************************/
  587.  
  588. void
  589. bump_current_hits_signature (void)
  590. {
  591.   unsigned char *hits = current_hits_signature;
  592.   while (*hits & 0x80)
  593.     *hits++ = 1;
  594.   *hits <<= 1;
  595. }
  596.  
  597. void
  598. init_hits_signature (int i)
  599. {
  600.   unsigned char *hits = current_hits_signature;
  601.   unsigned char const *end = ¤t_hits_signature[MAX_LEVELS];
  602.   while (hits < end)
  603.     {
  604.       *hits = 1 << (i & 7);
  605.       i >>= 3;
  606.       hits++;
  607.     }
  608. }
  609.  
  610. void
  611. free_summary_tokens (void)
  612. {
  613.   struct summary *summary = summary_leaf;
  614.   while (summary != summary_root)
  615.     {
  616.       free (summary->sum_tokens);
  617.       summary = summary->sum_parent;
  618.     }
  619. }
  620.  
  621. void
  622. summarize (void)
  623. {
  624.   unsigned char const *hits_sig = current_hits_signature;
  625.   struct summary *summary = summary_leaf;
  626.  
  627.   do
  628.     {
  629.       unsigned long count = summary->sum_hits_count;
  630.       unsigned char *hits = MALLOC (unsigned char, count + 1);
  631.       unsigned int level = summary->sum_level;
  632.       struct token **tokens = summary->sum_tokens;
  633.       unsigned long init_size = INIT_TOKENS_SIZE (summary->sum_level);
  634.  
  635.       if (verbose_flag)
  636.     printf (_("level %d: %ld/%ld = %.0f%%\n"),
  637.         summary->sum_level, count, init_size,
  638.         100.0 * (double) count / (double) init_size);
  639.  
  640.       qsort (tokens, count, sizeof (struct token *), token_qsort_cmp);
  641.       summary->sum_hits = hits;
  642.       while (count--)
  643.     {
  644.       unsigned char *hit = &(*tokens++)->tok_hits[level];
  645.       *hits++ = *hit;
  646.       *hit = 0;
  647.     }
  648.       *hits++ = 0;
  649.       if (summary->sum_parent)
  650.     {
  651.       free (summary->sum_tokens);
  652.       summary->sum_tokens = 0;
  653.     }
  654.       summary = summary->sum_parent;
  655.     }
  656.   while (*++hits_sig & 0x80);
  657.   summary_leaf = make_sibling_summary (summary_leaf);
  658. }
  659.  
  660. void
  661. init_summary (void)
  662. {
  663.   unsigned long size = INIT_TOKENS_SIZE (0);
  664.   summary_root = summary_leaf = CALLOC (struct summary, 1);
  665.   summary_root->sum_tokens_size = size;
  666.   summary_root->sum_tokens = MALLOC (struct token *, size);
  667. }
  668.  
  669. struct summary *
  670. make_sibling_summary (struct summary *summary)
  671. {
  672.   struct summary *parent = summary->sum_parent;
  673.   unsigned long size;
  674.  
  675.   if (parent == NULL)
  676.     {
  677.       levels++;
  678.       summary_root = summary->sum_parent = parent = CALLOC (struct summary, 1);
  679.       parent->sum_level = levels;
  680.       parent->sum_kids[0] = summary;
  681.       parent->sum_hits_count = summary->sum_hits_count;
  682.       parent->sum_free_index = 1;
  683.       size = INIT_TOKENS_SIZE (levels);
  684.       if (summary->sum_tokens_size >= size)
  685.     {
  686.       parent->sum_tokens_size = summary->sum_tokens_size;
  687.       parent->sum_tokens = summary->sum_tokens;
  688.     }
  689.       else
  690.     {
  691.       parent->sum_tokens_size = size;
  692.       parent->sum_tokens = REALLOC (summary->sum_tokens, struct token *, size);
  693.     }
  694.       summary->sum_tokens = 0;
  695.     }
  696.   if (parent->sum_free_index == 8)
  697.     parent = make_sibling_summary (parent);
  698.   summary = CALLOC (struct summary, 1);
  699.   summary->sum_level = parent->sum_level - 1;
  700.   parent->sum_kids[parent->sum_free_index++] = summary;
  701.   summary->sum_parent = parent;
  702.   size = INIT_TOKENS_SIZE (summary->sum_level);
  703.   summary->sum_tokens_size = size;
  704.   summary->sum_tokens = MALLOC (struct token *, size);
  705.   return summary;
  706. }
  707.  
  708. int
  709. count_vec_size (struct summary *summary, unsigned char const *tail_hits)
  710. {
  711.   struct summary **kids;
  712.   unsigned int hits = (summary->sum_hits ? *summary->sum_hits : *tail_hits);
  713.  
  714.   kids = summary->sum_kids;
  715.   if (*kids == NULL)
  716.     {
  717.       static char bits_per_nybble[] = { 0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4 };
  718.       return bits_per_nybble[hits & 0xf] + bits_per_nybble[hits >> 4];
  719.     }
  720.   else
  721.     {
  722.       int bit;
  723.       int count = 0;
  724.       --tail_hits;
  725.       for (bit = 1; bit & 0xff; bit <<= 1, ++kids)
  726.     if (bit & hits)
  727.       count += count_vec_size (*kids, tail_hits);
  728.       return count;
  729.     }
  730. }
  731.  
  732. int
  733. count_buf_size (struct summary *summary, unsigned char const *tail_hits)
  734. {
  735.   struct summary **kids;
  736.   unsigned int hits = (summary->sum_hits ? *summary->sum_hits : *tail_hits);
  737.  
  738.   kids = summary->sum_kids;
  739.   if (*kids == NULL)
  740.     return 1;
  741.   else
  742.     {
  743.       int bit;
  744.       int count = 1;
  745.       --tail_hits;
  746.       for (bit = 1; bit & 0xff; bit <<= 1, ++kids)
  747.     if (bit & hits)
  748.       count += count_buf_size (*kids, tail_hits);
  749.       return count;
  750.     }
  751. }
  752.  
  753. void
  754. assert_hits (struct summary* summary)
  755. {
  756.   struct summary **kids = summary->sum_kids;
  757.   struct summary **end = &kids[8];
  758.  
  759.   assert (summary->sum_hits == NULL || *summary->sum_hits == 0);
  760.  
  761.   if (end[-1] == 0)
  762.     while (*--end == 0)
  763.       ;
  764.   while (kids < end)
  765.     assert_hits (*kids++);
  766. }
  767.  
  768. void
  769. write_hits (FILE *fp, struct summary *summary, unsigned char const *tail_hits)
  770. {
  771.   struct summary **kids;
  772.   unsigned int hits = (summary->sum_hits ? *summary->sum_hits++ : *tail_hits);
  773.  
  774.   assert (hits);
  775.   putc (hits, fp);
  776.  
  777.   kids = summary->sum_kids;
  778.   if (*kids)
  779.     {
  780.       int bit;
  781.       --tail_hits;
  782.       for (bit = 1; (bit & 0xff) && *kids; bit <<= 1, ++kids)
  783.     if (bit & hits)
  784.       write_hits (fp, *kids, tail_hits);
  785.     }
  786. }
  787.  
  788. void
  789. sign_token (struct token *token)
  790. {
  791.   unsigned char *tok_hits = token->tok_hits;
  792.   unsigned char *hits_sig = current_hits_signature;
  793.   unsigned char *end = ¤t_hits_signature[MAX_LEVELS];
  794.   struct summary *summary = summary_leaf;
  795.  
  796.   while (summary)
  797.     {
  798.       if (*tok_hits == 0)
  799.     add_token_to_summary (summary, token);
  800.       if (*tok_hits & *hits_sig)
  801.     break;
  802.       *tok_hits |= *hits_sig;
  803.       summary = summary->sum_parent;
  804.       tok_hits++;
  805.       hits_sig++;
  806.     }
  807.   while (hits_sig < end)
  808.     {
  809.       if (*tok_hits & *hits_sig)
  810.     break;
  811.       *tok_hits |= *hits_sig;
  812.       tok_hits++;
  813.       hits_sig++;
  814.     }
  815. }
  816.  
  817. void
  818. add_token_to_summary (struct summary *summary, struct token *token)
  819. {
  820.   unsigned long size = summary->sum_tokens_size;
  821.  
  822.   if (summary->sum_hits_count >= size)
  823.     {
  824.       size *= 2;
  825.       summary->sum_tokens = REALLOC (summary->sum_tokens, struct token *, size);
  826.       summary->sum_tokens_size = size;
  827.     }
  828.   summary->sum_tokens[summary->sum_hits_count++] = token;
  829. }
  830.